/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
// 二分的本质是二段，而非单调
var search = function (nums, target) { 
    if(nums.length == 0) return -1
    if(nums.length == 1) return nums[0] === target ? 0 : -1
    let l = 0, r = nums.length - 1
    while(l < r) {
        // 因为这里取l时，算了mid所以要+1防止死循环
        let mid = Math.floor((l + r + 1) /2) // +1为了防止死循环
        if(nums[mid] >= nums[0]) {
            l = mid
        } else {
            r = mid - 1
        }
    }
    if(target >= nums[0]) {
        l = 0
    } else {
        l = l + 1
        r = nums.length - 1
    }
    while(l <= r) {
        let mid = Math.floor((l + r) /2)
        if(nums[mid] ===  target) return mid
        if(nums[mid] < target) {
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return -1
}
// console.log(search([4, 5, 6, 7, 0, 1, 2], 3))
// console.log(search([1], 0))
console.log(search([3, 4, 5, 6, 1, 2], 2))
// console.log(search([5, 1, 3], 5))
// console.log(search([5, 1, 3], 5))
// console.log(search([6, 7, 1, 2, 3, 4, 5], 6))